\chapter{Intelligence Artificielle}
Le jeu de Reversi est un jeu de stratégie combinatoire abstrait :
\begin{itemize}
\item il opppose deux joueurs ou deux équipes (ou seul contre un ordinateur "intelligent")
\item les joueurs ou équipes jouent à tour de rôle
\item tous les éléments sont connus (jeu à information complète)
\item le hasard n'intervient pas pendant le déroulement du jeu.
\end{itemize}

Il existe un bon nombre d'algorithmes de jeu permettant de jouer efficacement à ce type de jeu car à tout moment, il est possible de calculer toutes les solutions possibles amenant à la victoire. Biensûr ce calcul à un coup, et malgré la puissance toujours grandissante de nos machines, ce n'est pas toujours confortable de les faire fonctionner.
Grâce à ce jeu, nous allons mettre en appliction direct un des algorithmes vu en cours : l'algorithme du Min-Max et son optimisation, Alpha-Beta.
 
\section{Algorithme Min-Max}
\subsection{Idée générale}
Pour commencer, rappelons l'idée du Min-Max. Il s'agit d'examiner à partir de la situation courante toutes les évolutions possibles du jeu et ainsi pouvoir jouer le meilleur coup. Cet examen prend la forme d'un arbre, dont la profondeur correspond au nombre de coups joués par les 2 joueurs. Chaque noeud représente une évolution possible. La racine représente la situation de départ du calcul. Le nombre de noeuds d'un niveau de l'arbre correspond aux nombres de coups possibles à partir de la situation mère. La figure~\ref{arbreminmax} illustre cette idée.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.3]{arbreminmax.png}
\caption{Représentation d'un arbre Min-Max}
\label{arbreminmax}
\end{center}
\end{figure}
Pour exploiter cet arbre, il va falloir valuer les situations pour donner un poids aux différentes branches et choisir laquelle prendre pour jouer. Cette valuation est calculée par une fonction d'évaluation, nous la présenterons dans une seconde partie. Notons simplement que le principe de valution est de minimiser les coups de l'adversaire, et de maximiser les siens (d'où le nom de l'algoritme Min-Max).
Mais l'ensemble de ces calculs devient très vite couteux : la croissance de l'arbre est exponentielle et il devient vite impossible de calculer l'arbre profondément, et donc de prévoir le réel meilleur coup. 
C'est pour cela qu'il existe une amélioration simple du Min-Max qui remédie en partie à ce problème de coût.

\subsection{Alpha-Beta}
L'Alpha-Beta est une simple optimisation de l'algorithme Min-Max. La stratégie globale ne change pas mais on ne va plus calculer les situations (et donc les branches) qui n'en valent pas la peine. Cet élagage apporte un gain énorme dans la rapidité d'exécution. Il consiste juste, par un test simple qui compare les évalutions à 2 niveaux simultanément, d'oublier des parties de l'arbre dont on sait qu'on ne pourra pas calculer un coup intéressant.

\subsection{Notre implémentation}

Notre programme implémente directement l'aglorithme Alpha-Beta. Nous avons considéré qu'il n'était pas nécessaire de dissocier Min-Max et Alpha-Beta pour ce projet, l'objectif étant de fournir un programme capable de jouer efficacement dans des temps raisonnable. D'autant plus que ces 2 algorithmes donnent strictement les mêmes résultats, Alpha-Beta  le rendant plus rapidement.\\
Il y a 2 méthodes pour mettre en place l'algorithme Min-Max.
La première s'effectue en 2 temps : on commence par construire l'arbre (d'une profondeur donnée) puis avec un parcours en profondeur on évalue toutes les situations. Cette méthode est très couteuse en temps et peu adaptée à l'algorithme Alpha-Beta. Elle n'a pas de réel avantage face à la 2ème méthode.
L'autre méthode fonctionne de manière récursive. On ne construit pas d'arbre, mais on le parcours de manière virtuelle. Cette méthode correspond à l'implémentation du cours. Et elle offre tous ses avantages lorsque l'on optimise avec Alpha-Beta :  seules les branches intéressante sont parcourus.\\
Nous avons donc tout naturellement utilisé la seconde version dans notre programme.
Le code implémentant notre IA est donc organisé autour de 5 fonctions :
\begin{itemize}
\item \emph{Alpha-Beta} : cette fonction initialise le calcul. C'est elle qui renverra la position du coup à jouer.
\item \emph{Valeur}, \emph{Min} et \emph{Max} : ce sont ces 3 fonctions qui mettent en place la récursivité, de manière croisée. Elles permettent de parcourir virtuellement l'arbre jusqu'à une profondeur donnée et de lancer l'évaluation de la situation si besoin.
\item La fonction d'évalution : c'est la fonction qui évalue la situation.
\end{itemize}

Toutes ces fonctions font directement référence au cours. Elles ont juste bénéficié d'une adaption en JAVA pour répondre à notre problématique.

\section{Fonction d'évaluation}
La fonction d'évaluation est un élément important pour fournir un algorithme "intelligent". Nous avons vu que c'est à l'aide de cette fonction que l'on évalue les différentes situations. Finalement, c'est elle qui permet de traduire au mieux les règles du jeu, et les stratégies à adopter.
Il est possible de définir tout un tas de fonctions d'évaluation pour le jeu Reversi. La notre est relativement simple. N'ayant pas d'expérience à ce jeu, nous sommes partis du constat qu'il fallait avoir le maximun de pions de sa couleur pour gagner. Nous avons donc écrit une fonction d'évaluation qui compte le nombre de pions de sa couleur.
Evaluer une situation consistera alors à retourner le nombre de pions de sa couleur. Plus ce nombre sera élevé, plus le coup sera intéressant.

\medskip

D'autres fonctions, plus "intelligentes", seraient envisageables. On pourrait par exemple pondérer les cases du plateau pour attribuer plus ou moins de valeur à un coup. Le degré de stratégie de l'IA serait augmenté.\\
Une autre idée serait d'établir une base de coups à jouer en fonction des situations. Mais posséder une librairie de coup demande une légère expérience de jeu.
